#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTdatatype;
typedef struct BTnode
{
	BTdatatype val;
	struct BTnode* left;
	struct BTnode* right;
}BTnode, * PBTnode;
PBTnode Buynode(BTdatatype x)
{
	PBTnode node = (PBTnode)malloc(sizeof(BTnode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
PBTnode Createbinarytree()
{
	PBTnode node1 = Buynode(1);
	PBTnode node2 = Buynode(2);
	PBTnode node3 = Buynode(3);
	PBTnode node4 = Buynode(4);
	PBTnode node5 = Buynode(5);
	PBTnode node6 = Buynode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}
void Prevorder(PBTnode root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->val);
	Prevorder(root->left);
	Prevorder(root->right);
}
void Inorder(PBTnode root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Inorder(root->left);
	printf("%d ", root->val);
	Inorder(root->right);
}
void Postorder(PBTnode root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Postorder(root->left);
	Postorder(root->right);
	printf("%d ", root->val);
}
int size = 0;
void treesize(PBTnode root, int* psize)
{
	if (root == NULL)
		return 0;
	else
		(*psize)++;
	treesize(root->left, psize);
	treesize(root->right, psize);
}
int Treesize(PBTnode root)
{
	return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1;
}
int Treeleafsize(PBTnode root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return Treeleafsize(root->left) + Treeleafsize(root->right);
}
int Treeheight(PBTnode root)
{
	if (root == NULL)
		return 0;
	int leftheight = Treeheight(root->left);
	int rightheight = Treeheight(root->right);
	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
int fmax(int x, int y)
{
	return x > y ? x : y;
}
int TreeHeight(PBTnode root)
{
	if (root == NULL)
		return 0;
	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
int Treenodeksize(PBTnode root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return Treenodeksize(root->left, k - 1) + Treenodeksize(root->right, k - 1);
}
PBTnode Treenodefind(PBTnode root, BTdatatype x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	PBTnode ret1 = Treenodefind(root->left, x);
	if (ret1)
		return ret1;
	PBTnode ret2 = Treenodefind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;
}
bool Issametree(PBTnode root1, PBTnode root2)
{
	if (root1 == NULL && root2 == NULL)
		return true;
	if (root1 == NULL || root2 == NULL)
		return false;
	if (root1->val != root2->val)
		return false;
	return Issametree(root1->left, root2->left) && Issametree(root1->right, root2->right);
}
bool Issubtree(PBTnode root, PBTnode subroot)
{
	if (root == NULL)
		return false;
	if (root->val == subroot->val && Issametree(root, subroot))
		return true;
	return Issubtree(root->left, subroot) || Issubtree(root->right, subroot);
}
int TreeNodeSize(PBTnode root)
{
	return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}
void Prevorder(PBTnode root, int* arr, int* pi)
{
	if (root == NULL)
		return;
	arr[(*pi)++] = root->val;
	Prevorder(root->left, arr, pi);
	Prevorder(root->right, arr, pi);
}
int* PrevorderTraversal(PBTnode root, int* returnsize)
{
	*returnsize = TreeNodeSize(root);
	int* arr = (int*)malloc(sizeof(int) * (*returnsize));
	int i = 0;
	Prevorder(root, arr, &i);
	return arr;
}
int main()
{
	PBTnode root = Createbinarytree();
	//Prevorder(root);
	//Inorder(root);
	//Postorder(root);
	//printf("\n");
	//printf("N N 3 N 2 N N 5 N N 6 4 1");
	//printf("N 3 N 2 N 1 N 5 N 4 N 6 N");
	//printf("1 2 3 N N N 4 5 N N 6 N N");
	//int size = 0;
	//treesize(root, &size);
	//printf("%d\n", size);
	//size = 0;
	//treesize(root, &size);
	//printf("%d\n", size);
	//size = 0;
	//treesize(root, &size);
	//printf("%d\n", size);
	printf("%d\n", Treesize(root));
	printf("%d\n", Treeleafsize(root));
	printf("%d\n", TreeHeight(root));
	printf("%d\n", Treenodeksize(root, 3));
	return 0;
}
bool Isunivaltree(PBTnode root)
{
	if (root == NULL)
		return true;
	if (root->left && root->left->val != root->val)
		return false;
	if (root->right && root->right->val != root->val)
		return false;
	return Isunivaltree(root->left) && Isunivaltree(root->right);
}